package MyDFS;

import java.util.ArrayList;
import java.util.List;

/**
 * 全排列 第一项为0 最后一项为n
 */
public class Leetcode_jd {

    public static List<List<Integer>> permute(int[] nums) {
        // 首先是特判
        int len = nums.length;
        // 使用一个动态数组保存所有可能的全排列
        List<List<Integer>> res = new ArrayList<>();

        if (len == 0) {
            return res;
        }

        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();

        //
        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private static void dfs(int[] nums, int len, int depth,
                     List<Integer> path, boolean[] used,
                     List<List<Integer>> res) {
        if (depth == len && path.get(len-1) == len-1 && path.get(0) == 0) {
            // 3、不用拷贝，因为每一层传递下来的 path 变量都是新建的
            res.add(path);
            // System.out.println(path.toString());
            return;
        }

        // 第一位必须为0
        if(depth == 0){
            List<Integer> newPath = new ArrayList<>(path);
            newPath.add(nums[0]);

            boolean[] newUsed = new boolean[len];
            System.arraycopy(used, 0, newUsed, 0, len);
            newUsed[0] = true;

            dfs(nums, len, depth + 1, newPath, newUsed, res);
        }else{
            for (int i = 1; i < len; i++) {
                if (!used[i] && Math.abs(path.get(depth-1) - nums[i]) <= 2) {
                    // 1、每一次尝试都创建新的变量表示当前的"状态"
                    List<Integer> newPath = new ArrayList<>(path);
                    newPath.add(nums[i]);

                    boolean[] newUsed = new boolean[len];
                    System.arraycopy(used, 0, newUsed, 0, len);
                    newUsed[i] = true;

                    dfs(nums, len, depth + 1, newPath, newUsed, res);
                    // 2、无需回溯
                }
            }
        }
    }

    public static void main(String[] args) {
        for(int pp=1; pp<=10; pp++){
            int num = pp;
            int[] nums = new int[num+1];
            for(int index=0; index<=num; index++){
                nums[index] = index;
            }
            List<List<Integer>> permute1 = permute(nums);
            System.out.println(permute1.size());
        }
    }
}

